package io.github.hadyang.leetcode.offer;

import io.github.hadyang.leetcode.TreeLinkNode;

/** @author haoyang.shi */
public class GetNext {

  public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) return null;

    TreeLinkNode parent = pNode.next;
    if (pNode.right == null) {
      if (parent == null) {
        return null;
      }

      // 右节点
      if (parent.right == pNode) {
        TreeLinkNode cursor = parent;
        while (true) {
          TreeLinkNode p = cursor.next;
          if (p == null) return null;

          if (cursor == p.left) return p;

          cursor = p;
        }

      } else {
        return parent;
      }

    } else {
      TreeLinkNode cursor = pNode.right;
      while (cursor.left != null) {
        cursor = cursor.left;
      }

      return cursor;
    }
  }
}
